class Solution {
public:
    string minNumber(vector<int>& nums) {
        if(nums.size() == 0)  return "";
        /*
        按最高位排序后转换成字符串，其时间复杂度为O(nlogn + n)
        */
        sort(nums.begin(), nums.end(), lessmark);

        //首先确定首位的元素，不能为0
        string result;
        int sizeOfNums = nums.size();

        //按自定义排序顺序依次将数组中元素添加入字符串
        for(int i = 0; i < sizeOfNums; ++i)
        {
            result.append(to_string(nums[i]));
        }

        return result;
    }

    static bool lessmark(const int& a, const int& b)
    {
    	//自定义按最高位大小升序排序,若最高为相同，则比较第二位。。。
	    int a_copy = a;
	    int b_copy = b;
	    int a_tens = 1;
	    int b_tens = 1;
	    while (a_copy / a_tens >= 10)  a_tens *= 10;
	    while (b_copy / b_tens >= 10)  b_tens *= 10;

	    int a_start = a_copy / a_tens;
	    int b_start = b_copy / b_tens;

	    while (a_tens >= 10 || b_tens >= 10)
	    {
	    	if (a_copy / a_tens < b_copy / b_tens)  return true;
	    	else if (a_copy / a_tens > b_copy / b_tens)  return false;

	    	//若a>b，则比较完相同位数后，则需比较较小值的首位与较大值的剩余位
	    	if (a_tens >= 10)
	    	{
	    		a_copy -= ((a_copy / a_tens) * a_tens);
	    		a_tens /= 10;
	    	}
	    	else
	    	{
	    		a_copy = a_start;
	    	}

	    	if (b_tens >= 10)
	    	{
	    		b_copy -= ((b_copy / b_tens) * b_tens);
	    		b_tens /= 10;
	    	}
	    	else
	    	{
	    		b_copy = b_start;
	    	}
	    }

        //示例：12，121的比较;830,8308的比较
	    if (a_copy == b_copy)
	    {
	    	//暴力法比较
	    	string a_s = to_string(a);
	    	string b_s = to_string(b);
	    	int a_int = stoi(a_s + b_s);
	    	int b_int = stoi(b_s + a_s);
	    	return a_int < b_int;
	    }

	    return a_copy < b_copy;
    }
};

/******************************************************************************************/
class Solution {
public:
    string minNumber(vector<int>& nums) {
        if(nums.size() == 0)  return "";
        /*
        按最高位排序后转换成字符串，其时间复杂度为O(nlogn + n)
        */
        sort(nums.begin(), nums.end(), lessmark);

        //首先确定首位的元素，不能为0
        string result;
        int sizeOfNums = nums.size();

        //按自定义排序顺序依次将数组中元素添加入字符串
        for(int i = 0; i < sizeOfNums; ++i)
        {
            result.append(to_string(nums[i]));
        }

        return result;
    }

    static bool lessmark(const int& a, const int& b)
    {
        //直接暴力比较法
	    string a_s = to_string(a);
	    string b_s = to_string(b);
		//存在大数问题,直接转字符串比较
	    long long a_int = stoll(a_s + b_s);
	    long long b_int = stoll(b_s + a_s);
	    return a_int < b_int;
    }
	
	static bool lessmark2(const int& a, const int& b)
	{
		//直接暴力比较法,解决大数问题
		string a_s = to_string(a);
		string b_s = to_string(b);

		char* a_plus_b = new char[a_s.size() + b_s.size() + 1];
		strcpy(a_plus_b, a_s.data());
		strcat(a_plus_b, b_s.data());

		char* b_plus_a = new char[a_s.size() + b_s.size() + 1];;
		strcpy(b_plus_a, b_s.data());
		strcat(b_plus_a, a_s.data());

		return strcmp(a_plus_b, b_plus_a);
	}
};